package structures.huffmancode;


import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;

public class HuffManCodeDemo {
    private static final Map<Byte, String> huffManCodes = new HashMap<>();

    public static void main(String[] args) {
        String stringData = "i like like like java do you like a java l";
        System.out.println(Arrays.toString(stringData.getBytes()));
        // 获取 huffman 编码数据
        byte[] huffManCode = encoderHuffManCode(stringData.getBytes());
        System.out.println(Arrays.toString(huffManCode));
        // 把huffman编码数据解码
        String decodeHuffManCode = decodeHuffManCode(huffManCode);
        System.out.println(decodeHuffManCode + "----");
    }


    private static byte[] encoderHuffManCode(byte[] bytes) {
        if (bytes == null || bytes.length == 1) {
            return bytes;
        }
        // 统计每个字符出现的次数(权重)
        Map<Byte, Integer> countMap = new HashMap<>();
        for (byte data : bytes) {
            countMap.merge(data, 1, Integer::sum);
        }
        // 把 countMap 转换为list 为huffmanTree做准备
        List<Node> nodeList = new ArrayList<>();
        for (Map.Entry<Byte, Integer> entry : countMap.entrySet()) {
            nodeList.add(new Node(entry.getKey(), entry.getValue()));
        }
        // 把list转换为 huffmanTree
        while (nodeList.size() > 1) {
            // 按照权重大小进行排列
            nodeList.sort(null);
            Node nodeLeft = nodeList.get(0);
            Node nodeRight = nodeList.get(1);
            Node nodeParent = new Node(null, nodeLeft.getWeight() + nodeRight.getWeight());
            nodeParent.setLeftNode(nodeLeft);
            nodeParent.setRightNode(nodeRight);
            nodeList.remove(nodeLeft);
            nodeList.remove(nodeRight);
            nodeList.add(nodeParent);
        }
        Node nodeRoot = nodeList.get(0);

        // 根据 huffmanTree 获取 每个字符转换后对应的值
        getHuffManHashCode(nodeRoot, "");
        for (Map.Entry<Byte, String> entry : huffManCodes.entrySet()) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
        // 把原始bytes 转换为 huffman string(二进制的string)
        StringBuilder stringBuilder = new StringBuilder();
        for (byte data : bytes) {
            stringBuilder.append(huffManCodes.get(data));
        }
        System.out.println(stringBuilder.toString());
        // 根据二进制的string 转换为 10进制数据
        byte[] huffManByteCodes = new byte[(stringBuilder.length() + 7) / 8 + 1];   // 此处多申请了一个空间  用来记录前一个数据的位数(因为最后一个数的位数不可控)
        byte len = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            StringBuilder substring;
            if (i + 8 > stringBuilder.length()) {
                substring = new StringBuilder(stringBuilder.substring(i));
                len = (byte) substring.length();
            } else {
                substring = new StringBuilder(stringBuilder.substring(i, i + 8));
            }
            huffManByteCodes[i / 8] = (byte) Integer.parseInt(substring.toString(), 2);
        }
        huffManByteCodes[huffManByteCodes.length - 1] = len;
        return huffManByteCodes;
    }

    private static String decodeHuffManCode(byte[] bytes) {
        // 把字节数组转换为huffman编码的二进制字符串
        StringBuilder stringBuilder = new StringBuilder();
        int len = bytes[bytes.length - 1];
        for (int index = 0; index < bytes.length - 1; index++) {
            String binaryString = getBinaryString(bytes[index]);
            // 把最后一个数据的前置0去掉~
            if (index == bytes.length - 2 && len != 0) {
                // TODO: 2020/12/11 此处有问题  实在不想调了 末尾以 空格+l 会出现死循环  其实就是编码的时候 最后一个数据位 0xxx的时候 编程byte 0会被省略
                // TODO: 2020/12/11 暂时不知道该怎么处理 这里只是把最后一个 byte转成二进制字符串的时候把0去掉了
                // TODO: 2020/12/11 解决了  我在编码的时候 末尾多了一个数据 用来记录最后一个有效数据的位数 然后在此处解码的时候还原有效位数
                while (binaryString.length() > len) {
                    binaryString = binaryString.substring(1);
                }
            }
            System.out.println(binaryString);
            stringBuilder.append(binaryString);
        }

        // 把huffman编码的字符串还原为原来的字符串
        String decodeHuffManCode = stringBuilder.toString();
        Map<String, Byte> reverseHuffManHash = new HashMap<>();
        List<Byte> retList = new ArrayList<>();
        for (Map.Entry<Byte, String> entry : huffManCodes.entrySet()) {
            reverseHuffManHash.put(entry.getValue(), entry.getKey());
        }

        while (decodeHuffManCode.length() > 0) {
            for (int length = 1; length <= decodeHuffManCode.length(); length++) {
                String key = decodeHuffManCode.substring(0, length);
                if (reverseHuffManHash.containsKey(key)) {
                    retList.add(reverseHuffManHash.get(key));
                    decodeHuffManCode = decodeHuffManCode.substring(length);
//                    System.out.println(reverseHuffManHash.get(key));
                    break;
                }
            }
        }
        byte[] retByteArray = new byte[retList.size()];
        for (int index = 0; index < retList.size(); index++) {
            retByteArray[index] = retList.get(index);
        }
        return new String(retByteArray);
    }

    /**
     * 获取 huffManCodes 值
     *
     * @param node
     * @param value
     */
    private static void getHuffManHashCode(Node node,
                                           String value) {
        if (node == null) {
            return;
        }
        // 为叶子节点
        if (node.getData() != null) {
            huffManCodes.put(node.getData(), value);
            return;
        }
        // 为非叶子节点
        getHuffManHashCode(node.getLeftNode(), value + "0");
        getHuffManHashCode(node.getRightNode(), value + "1");
    }

    /**
     * 把byte数据转为8位二进制字符串)】
     *
     * @param data byte类型的数据
     * @return
     */
    private static String getBinaryString(byte data) {
        // 惊为天人  太刺激了 https://blog.csdn.net/hemin1003/article/details/54631008
        // data & 0xff 是为了防止负数问题, &0xff把数据控制在8位
        // + 0x100).substring(1) 是为了多出来以为保证中间为零的部分不被省略 然后从下标为1的位置开始截取字符串
        return Integer.toBinaryString((data & 0xff) + 0x100).substring(1);
    }
}

// 创建Node 包含 数据与权值
class Node implements Comparable<Node> {
    private Byte data;
    private int weight;
    private Node leftNode;
    private Node rightNode;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public void preOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.getLeftNode().preOrder();
        }

        if (this.getRightNode() != null) {
            this.getRightNode().preOrder();
        }
    }

    public Byte getData() {
        return data;
    }

    public void setData(Byte data) {
        this.data = data;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.getWeight() - o.getWeight();
    }
}
